public class Solution1240 {

    int ans=Integer.MAX_VALUE;

    public int tilingRectangle(int n, int m) {
        int[][] f=new int[n][m];
        dfs(f,0);
        return ans;
    }

    private void dfs(int[][] f,int step) {
        if (step>=ans){
            return;
        }
        int x=-1,y=-1;
        for (int i=0;i<f.length;i++){
            for (int j=0;j<f[0].length;j++){
                if (f[i][j]==0){
                    x=i;
                    y=j;
                    break;
                }
            }
            if (x!=-1){
                break;
            }
        }
        if (x==-1){
            ans=step;
            return;
        }
        for (int i=13;i>=1;i--){
            if (x+i-1<f.length && y+i-1<f[0].length){
                boolean flag=true;
                for (int j=1;j<=i;j++){
                    for (int k=1;k<=i;k++){
                        if (f[x+j-1][y+k-1]==1){
                            flag=false;
                            break;
                        }
                    }
                    if (!flag){
                        break;
                    }
                }
                if (flag){
                    for (int j=1;j<=i;j++){
                        for (int k=1;k<=i;k++){
                            f[x+j-1][y+k-1]=1;
                        }
                    }
                    dfs(f,step+1);
                    for (int j=1;j<=i;j++){
                        for (int k=1;k<=i;k++){
                            f[x+j-1][y+k-1]=0;
                        }
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(new Solution1240().tilingRectangle(11,13));
    }
}
